`
https://leetcode.cn/problems/subarray-sums-divisible-by-k/
`

/**
 * @param {number[]} nums
 * @param {number} k
 * @return {number}
 */
var subarraysDivByK = function (nums, k) {
  const n = nums.length

  // 计算前缀和
  const prefix = new Array(n + 1)
  prefix[0] = 0
  for (let i = 1; i < prefix.length; i++) {
    prefix[i] = prefix[i - 1] + nums[i - 1]
  }

  let res = 0

  // 哈希表存储前缀和出现过的次数
  const counts = new Map()
  for (let i = 0; i < prefix.length; i++) {
    // 计算出当前前缀和要符合结果的差值
    let need = prefix[i] % k
    // 如果出现了负数，还需要加上 k 补成正数
    if (need < 0) need += k

    // 如果之前存在 need，说明之前存在至少一个可被 k 整除的非空子数组
    // 后将 need 的出现次数记录进哈希表
    if (counts.has(need)) {
      const count = counts.get(need)
      res += count
      counts.set(need, count + 1)
    } else {
      counts.set(need, 1)
    }
  }

  return res
};